vector<Int8> Shift, Gray;
vector<Int64> M;

void nshift(int s, int e, int k) {
  const int n = e - s;
  if (k == 0 || n == 1) return ;

  const int t = k/n;
  const bool vect = !(t & 1);
  const int knm1 = k % n;

  if (knm1 != 0) {
    if (vect) Shift.push_back(s+knm1-1);
    else Shift.push_back(e-knm1-1);
  } else {
    if (vect) nshift(s+1, e, t);
        else nshift(s, e-1, t);
  }
}

inline int fact(int n) {
  int res = n;
  for(int i = 2; i < n; i++) res *= i;
  return res;
}

inline Int32 graycode(Int32 b) {
  return b ^ (b >> 1);
}

inline int log2(Int32 b) {
  int r = 0;
  while (b != 1) {
    r++;
    b >>= 1;
  }                                     
  return r;
}

inline void MakeAddArrays(Int8 n) {
  //построение Shift-массива (массива перестановок)
  Shift.clear();
  int shiftcol = fact(n); Shift.push_back(0);
  for(int i = 0; i < shiftcol; i++) {
    nshift(0, n, i);
  } 
  
  //построение Gray-массива (массив, который содержит значения кода-Грея)
  const Int32 ton = (1 << n);
  Int32 onegmask = 0;
  Gray.resize(ton);
  Gray[0] = 0;
  for(Int32 i = 1; i < ton; i++) {
    const Int32 negmask = graycode(i);
    const Int32 rnegmask = negmask^onegmask;
    onegmask = negmask;
    Gray[i] = log2(rnegmask);
  }
  
  //Построение различных масок
  int cs = 1;
  M.resize(n);
  for(int i = n; i--; ) {
    M[i] = 0;
    int t = 1;
    for(int j = 0; j < (1 << n) / cs; j++) {
      for(int ij = cs; ij--; ) M[i] = (M[i] << 1)+t;
      if (t == 0) t = 1; else t = 0;
    }
    cs = cs << 1;
  }
}



inline Int64 swapvars(const Int64 f, Int8 va, const Int8 n) {
  const Int8 vb = va; va++;
  const Int64 sm = M[va] ^ M[vb];
  const Int64 apm = sm & M[va];
  const Int64 bpm = sm & ~M[va];

  const int sd =  (1 << (n - vb - 1)) - (1 << (n - va - 1));
  return (f & ~sm) + ((f & apm) << sd) + ((f & bpm) >> sd);
}

inline Int64 negbyvar(const Int64 f, const Int8 v, const Int8 n) {
  const Int8 sd = 1 << (n - v - 1);
  return ((f & M[v]) >> sd) + ((f & ~M[v]) << sd);
}

//x0 - d
inline Int64 d1byvar(const Int64 f, const Int8 v, const Int8 n) {
  const Int8 sd = 1 << (n - v - 1);
  const Int64 d = ((f & M[v])>>sd) ^ ((f & ~M[v]));
  return ((f & M[v])) + d;
}

//d - x0
inline Int64 d2byvar(const Int64 f, const Int8 v, const Int8 n) {
  const Int8 sd = 1 << (n - v - 1);
  const Int64 d = ((f & M[v])) ^ ((f & ~M[v]) << sd);
  return ((f & M[v]) >> sd) + d;
}

//x1 - d
inline Int64 d3byvar(const Int64 f, const Int8 v, const Int8 n) {
  const Int8 sd = 1 << (n - v - 1);
  const Int64 d = ((f & M[v])>>sd) ^ ((f & ~M[v]));
  return ((f & ~M[v]) << sd) + d;
}

//d - x1
inline Int64 d4byvar(const Int64 f, const Int8 v, const Int8 n) {
  const Int8 sd = 1 << (n - v - 1);
  const Int64 d = ((f & M[v])) ^ ((f & ~M[v]) << sd);
  return ((f & ~M[v])) + d;
}

